package com.learn.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

/**
 * 求质数
 */
public class GetPrime {
    private static List<Integer> func0_primeList = new ArrayList(){{add(3);}};

    //从func1演进而来，用以支持任意数，使用了List及迭代、递归，效率是最低
    private static void func0(int start, int end){
        long s = System.currentTimeMillis();
        AtomicInteger count = new AtomicInteger(1);
        funcRecursion(start, end,0, count);
        long e = System.currentTimeMillis();
        System.out.println("  -- func0: "+count.get()+", time:"+(e-s));
    }


    private static void funcRecursion(int start, int end,int first,AtomicInteger count){
        if(start>0){
            funcRecursion(0,start,first++,count);
        }

        Double sqrtd = Math.sqrt(end);
        int sqri = sqrtd.intValue();
        List<Integer> newPrimeList = func0_primeList.stream().filter(c->c<sqri).collect(Collectors.toList());
        for (int i = start; i <end ; i++) {
            if((i&1)==1){
                boolean f = true;
                for (int k1 : newPrimeList) {
                    count.addAndGet(1);
                    if(i%k1==0){
                        f = false;
                        break ;
                    }

                }
                if(f){
                    if(i>3){
                        newPrimeList.add(i);
                    }
                    if(first>0){
                        System.out.print(" "+i);
                    }
                }
            }
        }
        func0_primeList.addAll(newPrimeList);
        return;
    }

    //最先想到的方法，质数两个特性，首先是奇数，其次不能被本身外其他数除（其他数只考虑质数即可）。
    //本方法只适用于200以内，以为200开方后14，小于14的质数：{3,5,7,11,13};
    private static void func1(int start, int end){
        long s = System.currentTimeMillis();
        int [] k = new int[]{3,5,7,11,13};//小于14的质数

        List<Integer> result = new ArrayList<>();

        int count = 1;

        for (int i = start; i <=end ; i++) {
            if((i&1)==1){
                boolean f = true;
                for (int k1 : k) {
                    count++;
                    if(i%k1==0){
                        f = false;
                        break ;
                    }
                }

                if(f){
                    result.add(i);
                    System.out.print(" "+i);
                }

            }
        }
        long e = System.currentTimeMillis();
        System.out.println("  -- func1:"+count+", time:"+(e-s));
    }



    private static void func2(int start, int end){
        long s = System.currentTimeMillis();
        AtomicInteger count = new AtomicInteger(1);
        for(int i=start;i<=end;i++){
            boolean flag=true;
            //100包含所有特殊数据
            //for(int j=2;j<100;j++){
            for(int j=2;j<i;j++){
                count.addAndGet(1);
                if(i%j==0){
                    flag=false;
                    break;
                }
            }
            if(flag==true){
                System.out.print(" "+i);
            }
        }
        long e = System.currentTimeMillis();
        System.out.println("  -- func2: "+count.get()+", time:"+(e-s));
    }


    public static void func3(int start, int end){
        long s = System.currentTimeMillis();
        AtomicInteger count = new AtomicInteger(1);
        for(int i=start;i<=end;i++){
            count.addAndGet(1);
            boolean b = isPrime(i,count);
            if(b){
                System.out.print(" "+i);
            }
        }
        long e = System.currentTimeMillis();
        System.out.println("  -- func3: "+count.get()+", time:"+(e-s));
    }

    public static boolean isPrime(int num,AtomicInteger count) {
        if (num <= 3) {
            return num > 1;
        }
        // 不在6的倍数两侧的一定不是质数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sqrt = (int) Math.sqrt(num);
        for (int i = 5; i <= sqrt; i += 6) {
            count.addAndGet(1);
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args){

        int start = 101;
        int end = 200;

        func1(start,end);
        System.out.println("****");
        func2(start,end);
        System.out.println("****");
        func3(start,end);
        System.out.println("****");
        func0(start,end);
    }
}
